(1) Field of the Invention
The present invention relates generally to cryptography and, more particularly, to public key cryptographic systems such as RSA.
(2) Description of the Prior Art
With the enormous volume of data that is transmitted electronically throughout the world, methods for securing the privacy of that data are crucial to the economy. Before the 1970s, senders and recipients would need to agree on some sort of secret key in order to encrypt messages such that they could not be deciphered by unauthorized third parties but could still be read by the intended recipient. This sort of symmetric cryptography alone is inconvenient in the Internet age, where it is not always easy to arrange a meeting to exchange a secret password that will allow for future secure communications. Fortunately, public key cryptography was developed in the last few decades by Diffie, Hellman, Rivest, Shamir, and Adelman, among others.
Public key cryptography allows for the secure exchange of information between senders and recipients without the necessity that the two parties first exchange a secret key. The recipient simply makes his public key available, which can be used by anyone to encrypt a message to him. Once a message is encrypted using the recipient's public key, only the private key can be used to restore the message to its original state. Only the recipient knows his private key, so messages encrypted with the public key are secure.
The standard methods for public key cryptography were developed by Rivest, Shamir, and Adelman (RSA), described in U.S. Pat. No. 4,405,829. RSA and its variants provide for encryption of data using a public key and decryption using a private key.
RSA security has been publicly and commercially used for communicating or transmitting information, data, documents, messages, and files; however, it is relatively slow (especially the process of decryption) and computationally intensive. This presents problems in many implementations, including servers that receive a large number of requests and mobile devices that have a small amount of computing resources available to them. The slow speed of RSA is a result of the large numbers required to ensure the security of the algorithm. The RSA scheme capitalizes on the extreme difficulty of factoring a large composite number into its constituent primes.
RSA and CRT RSA
    RSA consists of three steps: key generation, encryption, and decryption.Key Generation    Key generation starts by deciding on an adequate length for what is called the public modulus N. This choice is dictated by the difficulty of factoring N into its prime factors. Right now, N of length 1024 bits is considered a sufficient size to prevent factoring. The bit length of N will continue to go up in the future. Next, two random prime numbers that are each half the length of N, p and q, are generated. Next, a small odd integer, e, is selected such that e is relatively prime to 1 cm(p−1, q−1). In practice, e is usually chosen to be 65537. In this paper, we will refer to e as the public exponent and N as the public modulus. The RSA public key consists of the two integers (e, N).
The private exponent, d, is a multiplicative inverse of e(mod 1 cm(p−1, q−1)), so that e*d=1 mod (1 cm(p−1, q−1)). Often, the private key refers to the set of numbers (p,q,d), so d should be referred to as the private exponent rather than as the private key.
Encryption
    To encrypt message X using an RSA public key {e, N}, one must first convert X into an integer M using a formatting operation. Encryption of M into ciphertext C is then accomplished by calculating C as the remainder after N is divided into M taken to the power of e. In equation form, C=Me mod N where M is an integer greater than −1 and less than N, 0≦M<N.Decryption    To decrypt using the original implementation of RSA, M is obtained by calculating the remainder after N is divided into C taken to the power of d. In equation form, M=Cd mod N. M is then converted back to X by reversing the same formatting operation that was used to obtain M from X originally.
It is standard practice now to use the Chinese Remainder Theorem (CRT) for RSA decryption. Rather than compute M=Cd mod N, one calculates dp=d mod (p−1) and dq=d mod (q−1). Then, one calculates Mp=Cdp mod p and Mq=Cdq mod q. Then, one uses CRT to calculate M from Mp and Mq. This is about four times as fast as calculating M=Cd mod N directly. For the remainder of this paper, we will refer to this method of RSA decryption as CRT RSA.
Since CRT RSA, a handful of improvements to the RSA methodology have been made to increase decryption speed. We will touch on each of these methods briefly, with more attention paid to Multi-Prime and Multi-Power RSA, which are more in the field of the present invention.
Multi-Prime RSA
    This method is detailed in U.S. Pat. No. 5,848,159. Multi-Prime RSA suggests the use of more than two distinct prime factors to generate the public modulus N, whereas the RSA method traditionally uses only two distinct prime factors. For a modulus N of length 1024 bits, Multi-Prime RSA chooses three prime numbers p, q, r that are each one third the length of N. The encryption process is exactly the same as traditional RSA. The decryption process for Multi-Prime RSA is relevantly similar to that of CRT RSA, except that three or more distinct prime numbers are used instead of two. In Multi-Prime RSA, like in traditional and CRT RSA, all of the distinct prime factors of the modulus N are used for decryption of messages.
Using multiple prime factors for RSA decryption increases the total number of calculations that need to be performed, but each calculation is less intensive since each prime factor is smaller than in the two-prime implementation. The result is a theoretical speedup of b2/4, where b is the number of prime factors used. With N of length 1024 bits and b set to 3 (the current maximum for security reasons), Multi-Prime RSA achieves a theoretical speedup of 2.25 over two-factor CRT RSA methods.
Multi-Power RSA
    This method is detailed in U.S. Patent Application 20020064278. This method is similar to the Multi-Prime method, except that the Multi-Prime method assumes that all of the prime numbers that make up the composite number N are distinct numbers. The Multi-Power method assumes that N is made up of more than two prime factors, but that N is only made up of exactly two distinct prime factors. So, if N=p*q*r, it is assumed that p=q and therefore N=p 2r. Like Multi-Prime RSA, encryption is performed in exactly the same was as traditional RSA. For decryption, Multi-Power RSA is able to capitalize on the fact that there are only two distinct prime numbers. So, only two large modular exponentiation computations are necessary (there are several smaller mathematical operations involved using this technique which are computationally negligible), providing increased efficiency over the Multi-Prime method. In Multi-Power RSA, like Multi-Prime and CRT RSA, all of the distinct prime factors of the modulus N are used for decryption of messages.
The result is a theoretical speedup of b3/8, where b is the number of prime factors used. With N of length 1024 bits and b set to 3 (the current maximum for security reasons), Multi-Power RSA achieves a theoretical speedup of 3.375 over two-factor CRT RSA methods.
Batch RSA
    Batch RSA is based on the idea that, in certain situations, two or more decryptions can be performed for the time cost of one. In order for this to work, very small public exponents must be used (such as 3 or 5). Further, the system only works if encryption is performed using different public exponents but the same public modulus. Further discussion of this technique is beyond the scope of this paper, but it is another example of a technique to speed up RSA decryption. With N of length 1024, it speeds up decryption by a factor of 2 or 3. However, there are many practical drawbacks to batch RSA techniques.Rebalanced RSA    In standard RSA, encryption is much faster than decryption. In many applications, it would be desirable to change this behavior. Rebalanced RSA simply shifts more of the burden to the encryption process by increasing the size of the public exponent e (which is usually set to 65537), and tries to decrease the size of the private exponents as much as possible without creating security problems. Rebalanced RSA can be used in conjunction with many of the other methods here, such as Multi-Prime or Multi-Power RSA.Hardware    There are also hardware approaches to speeding up RSA decryption. These methods consist of designing special processors or other hardware that is designed specifically for the type of modular arithmetic operations that RSA requires. Most hardware methods can be used in conjunction with the algorithmic methods described above.
Despite the existence of several software and hardware implementations for improving the overall speed of the decryption process in public key cryptography, there is still a need for continued improvements to the existing body of work. Faster decryption algorithms provide direct value in many situations, since companies that formerly needed two or three servers to handle decryption may now only need one etc. Given the fact that nearly all secure Internet traffic (SSL) current utilizes public key encryption/decryption, the present invention will provide great utility to the market.